//https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
//链表的回文结构
//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* slow = A;
        ListNode* fast = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* head = slow;
        ListNode* change = NULL;
        while(head)
        {
            struct ListNode* next = head->next;
            head->next = change;
            change = head;
            head = next;
        }
        
        while(change)
        {
            if(change->val != A->val)
            return false;
            change = change->next;
            A = A->next;
        }
        return true;
    }
};